//最大子数组
//给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//子数组 是数组中的一个连续部分。
//思路：
//连续索引——不能进行直接排序，可以通过结构体进行qsort快排，但索引依旧不方便
//特殊情况：只有一个元素，直接返回该元素作为子元素
//方法：贪心算法-》动态规划    三个元素，上一个和(prev)，最大和(max_sum)，当前值
//当当前和小于0时，抛弃当前和，从下一个元素重新计和
//，即当上一个和与当前值相加后与当前值相比，若小于，则直接从当前值开始计算,使用fmax（prev+nums[i],nums[i]）
//将每一个元素的当前和进行保存，最后从保存值里选取最大值即可。
//简化：一直保存最大和，通过与当前和进行比较，始终留下最大值.使用fmax(fmax,prev);
int maxSubArray(int* nums, int numsSize) {
	if (numsSize == 1)
		return nums[0];
	int prev, max;
	prev = 0, max = nums[0];
	//注意：max 初始值要是首元素，而不能是0，因为首元素可能为负值，当取0时，结果为0，当前最大和不符合实际
	for (int i = 0; i < numsSize; i++) {
		prev = fmax(prev + nums[i], nums[i]);
		max = fmax(max, prev);
	}
	return max;
}
